МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ЗВІТ
про виконання лабораторної роботи №2
з курсу:
«Алгоритмічні основи криптології»
ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ
Мета роботи: вивчити алгоритми множення та ділення довгих чисел та навчитися розробляти програмне забезпечення для реалізації цих алгоритмів на комп’ютері.
Завдання:
Скласти програму для реалізації операцій множення довгих чисел з використанням перетворення Фур’є.
Список ідентифікаторів констант, змінних і функцій, використаних у головній програмі і підпрограмах та їх пояснення
max – константа що вказує на максимальну довжину масиву;
оsn – константа що вказує на основу;
vvid() – ввід довгого числа з клавіатури;
vyvid()- вивід довгого числа на екран;
shpf() – знаходження ШПФ від числа;
dpf() – знаходження ДПФ від числа;
transf() – здійснює перенесення;
scal_mult() – здійснює скалярне множення двох векторів;
mult() – множення двох довгих чисел;
ch – елемент типу CHAR;
masCh – масив елементів типу CHAR;
a[], b[],c[] – масиви, що представляють довгі числа;
y[][], y1[][],y2[][] – двовимірні масиви, що представляють довгі числа;
i, j, k – цілі змінні, що використовуються в циклі;
N, NN, p, k, tt – проміжні змінні, що використовуються у підпрограмах.
Блок-схема алгоритму програми
Головна програма
функція vvid
функція vyvid
функція shpf
функція roun
функція dpf
функція mult
функція scal_mult
функція transf
Текст програми
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <conio.h>
#include <math.h>
#define max 100
#define osn 10000
#define Pi 3.141592653589793
long roun(double x);
void vvid(long a[max]);
void vyvid(long a[max]);
void shpf(long a[max], double y[max][2], int N);
void mult(long a[max], long b[max], long c[max]);
void scal_mult(double y1[max][2], double y2[max][2], double y[max][2]);
void transf(long c[max]);
void dpf(double y[max][2], long c[max], int N);
long int*vvid( char masCh[])
{
long int *a;
char ch;
a = (long int*)malloc(max*sizeof(int));
int i = 0;
int j = 0;
for(i = 0; i < max; i++)
{
a[i] = 0;
}
for(j = 0; masCh[j] !=0; j++)
{
if ( isdigit(masCh[j]) )
{
for (i = a[0]; i >= 1; i--)
{
a[i + 1] = a[i + 1] + (a[i] * 10) / osn;
a[i] = a[i] * 10 % osn;
}
ch = masCh[j];
int a22 = atoi(&ch);
a[1] = a[i+1] + a22;
if (a[a[0] + 1] > 0)
a[0]++;
}
}
return a;
}
void vyvid(long int *b)
{
int N = 0;
int NN = 1;
int p;
int b_Osn = b[0];
int i = 0;
for(i = b[0]; i>=1 ; i--)
{
N = b[i];
if (N == 0)
NN = 0;
for (p = 1; N > 0; p = p*10)
{
N = N / 10;
}
while (osn - p != 0)
{
if (b[0] == i)
break;
printf("%c",'0');
p = p*10;
}
if (NN == 1)
{
int result = b[i];
printf("%d",result);
}
NN = 1;
N = 0;
}
}
long int* mult (long int a[], long int b[])
{
long int *tt, *c; int j = 0, i = 0, k = 0;
tt = new long int[max]; c = new long int[max];
for(i = 0; i < max; i++)
{
tt[i] = 0;
}
c[0] = a[0];
for(i = 1; i <= b[0]; i = i+1)
{
for(j = 1; j <= c[0]; j++ )
{
c[j] = 0;
}
for(j = 1, k = i; j <= a[0]; j = j+1, k = k+1)
{
c[j+1] = (a[j]*b[i] + c[j] + tt[k])/osn;
c[j] = (a[j]*b[i] + c[j] + tt[k])%osn;
}
if(c[j] != 0) c[0] = c[0]+1;
for(j = i, k = 1; j <= c[0]; j= j+1, k = k+1)
{
tt[j] = c[k]; } tt[0] = c[0];
}
for(i = 1; i <= c[0]; i = i+1)
{
c[i] = tt[i];
}
return c;
}
void shpf(long a[max], double y[max][2], int N)
{
int i,j,k;
for(i=0;i<max;i++)
for(j=0;j<2;j++)
y[i][j]=0;
for(j=0;j<N;j++)
{
for(i=0;i<a[0];i++)
{
y[j][0]=y[j][0]+a[a[0]-i]*cos(2*Pi*i*j/N);
y[j][1]=y[j][1]+a[a[0]-i]*sin(2*Pi*i*j/N);
}
}
}
long roun(double x)
{
if(x>=0)
return ((long)(x+0.5));
else
return ((long)(x-0.5));
}
void dpf(double y[max][2], long c[ma...
